﻿//https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked

class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        int flag = 0;
        //把所有负数 0 大于n的数转变为1
        for (int& e : nums)
        {
            if (e == 1)
            {
                flag = 1;
            }
            if (e <= 0 || e > n)
            {
                e = 1;
            }
        }

        if (flag == 0)
        {
            return 1;
        }

        //标记出现过的正整数的位置为负数
        for (int i = 0; i < n; i++)
        {
            int num = abs(nums[i]);
            if (num <= n)
            {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }

        //找到第一个不为负数的位置
        for (int i = 0; i < n; i++)
        {
            if (nums[i] > 0)
            {
                return i + 1;
            }
        }
        return n + 1;

    }
};